/*
题目: 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。
 */
public class LargestRectangleArea {
    public int largestRectangleArea(int[] heights) {
        //单调栈
        Stack<Integer> stack = new Stack<> ();
        int squ = 0;//最大矩形面积
        int[] newHeights = new int[heights.length + 2];
        for (int i = 1; i < newHeights.length - 1; i++) {
            newHeights[i] = heights[i - 1];
        }

        //为了保证squ要更新过,我们要在数组头和尾分别加一个0
        for (int i = 0; i < newHeights.length; i++) {
            while (!stack.isEmpty() && newHeights[stack.peek()] > newHeights[i]) {
                int cur = stack.pop(); //弹出当前矩形下标
                int curHeight = newHeights[cur];//当前矩形的高度
                if (stack.isEmpty()) break;

                int left = stack.peek();//当前矩形下面的矩形(栈)
                int width = i - left - 1;
                int tmpSqu = curHeight * width;

                squ = Math.max(squ, tmpSqu);
            }
            stack.push(i);
        }

        return squ;
    }
}
